#include "../bin_tree/bin_tree.h"

template <typename T>
class BST : public BinTree<T>
{
protected:
    BinNodePosi(T) _hot;

public:
    virtual BinNodePosi(T) & search(const T &e);
    virtual BinNodePosi(T) insert(const T &e);
    virtual bool remove(const T &e);
};

template <typename T>
    BinNodePosi(T) & BST<T>::search(const T &e)
{
    if (!_root || e == _root->data)
    {
        _hot = NULL;
        return _root;
    }
    for (_hot = _root;;)
    {
        BinNodePosi(T) &c = (e < _hot->data) ? _hot->lc : _hot->rc;
        if (!c || e == c->data)
            return c;
        _hot = c;
    }
}

template <typename T>
BinNodePosi(T) BST<T>::insert(const T &e)
{
    BinNodePosi(T) &x = search(e);
    if (x)
        return x;
    x = new BinNode<T>(e, _hot);
    _size++;
    updateHeightAbove(x);
    return x;
}

template <typename T>
bool BST<T>::remove(const T &e)
{
    BinNodePosi(T) &x = search(e);
    if (!x)
        return false;
    removeAt(x, _hot);
    _size--;
    updateHeightAbove(_hot);
    return true;
}

/**
 *
 * @param  { BinNodePosi(T)& } x
 * @param  { BinNodePosi(T)& } hot
 * @return { BinNodePosi(T)  }
 */
template <typename T>
static BinNodePosi(T) removeAt(BinNodePosi(T) & x, BinNodePosi(T) & hot)
{
    BinNodePosi(T) w = x;
    BinNodePosi(T) succ = NULL;
    if (!HasLChild(*x))
        succ = x = x->lc;
    else if (!HasRChild(*x))
        succ = x = x->rc;
    else
    {
        w = w->succ();
        swap(x->data, w->data);
        BinNodePosi(T) u = w->parent;
        ((u == x) ? u->rc : u->lc) = succ = w->rc;
    }
    hot = w->parent;
    if (succ)
        succ->parent = hot;
    release(w->data);
    release(w);
    return succ;
}